package com.leetcode.string;

/**
 * @author Dennis Li
 * @date 2020/7/29 11:18
 */
public class CountSubstrings_647 {

    public int countSubstrings(String s) {
        if (s == null || s.equals("")) return 0;
        int n = s.length(), count = s.length();
        boolean[][] dp = new boolean[n][n];
        // 初始化
        char[] chars = s.toCharArray();
        for (int i = 0; i < n; i++) dp[i][i] = true;
        // 巧妙的一步。避免了对 i == j 这种情况的判断
        // 模拟前后双游标逼近的过程
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                // 如果是紧邻的数，那么一定为true
                // 如果不相等，肯定为false
                dp[i][j] = chars[i] == chars[j] && (j - i == 1 || dp[i + 1][j - 1]);
                if (dp[i][j]) count++;
            }
        }
        return count;
    }

    private int count = 0;

    public int countSubstrings2(String s) {
        for (int i = 0; i < s.length(); i++) {
            isPalindrome(s, i, i);
            isPalindrome(s, i, i + 1);
        }
        return count;
    }

    private void isPalindrome(String s, int i, int j) {
        while (i >= 0 && j < s.length() && s.charAt(i--) == s.charAt(j++)) {
            count++;
        }
    }

}
